package algorithm;

import java.util.*;

/**
 * @author apple
 * @Classname BreathFirstSearch
 * @Description 广度优先遍历
 * @Date 2020/4/18 15:00
 */
public class BreathFirstSearch {

    public static void bfsWithQueue(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        /**根节点入队**/
        queue.add(root);
        /**非空队列遍历**/
        while (!queue.isEmpty()) {
            /** 队列头部元素出队**/
            TreeNode treeNode = queue.poll();
            System.out.println(treeNode.value);
            /**获取左子节点**/
            TreeNode leftNode = treeNode.leftTreeNode;
            /**非空左子节点入队**/
            if (leftNode != null) {
                queue.add(leftNode);
            }
            /**获取右子节点**/
            TreeNode rightNode = treeNode.rightTreeNode;
            /**非空右子节点入队**/
            if (rightNode != null) {
                queue.add(rightNode);
            }
        }
    }

    /**按层级输出二叉树**/
    public static List<List<Integer>> bfsWithBinaryTree(TreeNode root){
        if(root ==null){
            /**根节点为空，直接返回空数组**/
            return Arrays.asList();
        }
        /**最终结果数组**/
        List<List<Integer>> resultList = new ArrayList<>();

        Queue<TreeNode> queue= new LinkedList<>();
        queue.add(root);

        while(!queue.isEmpty()){
            /**每一层的结果**/
            List<Integer> levelList= new ArrayList<>();
            int levelNum= queue.size();
            /**遍历当前层的节点**/
            for(int i=0;i<levelNum;i++){
                /**队头元素出队**/
                TreeNode treeNode = queue.poll();
                /**当前节点的左右子节点入队**/
                if(treeNode.leftTreeNode!=null){
                    queue.add(treeNode.leftTreeNode);
                }
                if(treeNode.rightTreeNode!=null){
                    queue.add(treeNode.rightTreeNode);
                }
                levelList.add(treeNode.value);
            }
            resultList.add(levelList);
        }
        return resultList;
    }




    public static void main(String[] args) {
        int[] list = {10, 25, 13, 1, 6, 11, 15};
        BinaryTree binaryTree =BinaryTreeBuilder.createBinaryTree(list);
        bfsWithQueue(binaryTree.getRoot());
        System.out.println("按层级输出二叉树");
        List<List<Integer>> resultList =bfsWithBinaryTree(binaryTree.getRoot());
        for(int i=0;i<resultList.size();i++){
            List<Integer> levelList = resultList.get(i);
            for(int j=0;j<levelList.size();j++){
                System.out.print(levelList.get(j));
                if(j<levelList.size()-1){
                    System.out.print(",");
                }
            }
            System.out.println();
        }
    }
}
